//
// Created by xili on 2024/9/20 19:24.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution1 {
public:
    vector<int> durations = {1, 7, 30};

    int mincostTickets(vector<int> &days, vector<int> &costs) {
        return f(days, costs, 0);
    }

    int f(vector<int> &days, vector<int> &costs, int i) {
        if (i == days.size()) {
            return 0;
        }
        int ans = INT32_MAX;
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.size() && days[i] + durations[k] > days[j]) {
                j++;
            }
            ans = min(ans, costs[k] + f(days, costs, j));
        }
        return ans;
    }
};

//记忆化搜索
class Solution2 {
public:
    vector<int> durations = {1, 7, 30};

    int mincostTickets(vector<int> &days, vector<int> &costs) {
        vector<int> dp(366, -1);
        return f(days, costs, 0, dp);
    }

    int f(vector<int> &days, vector<int> &costs, int i, vector<int> &dp) {
        if (dp[i] != -1) {
            return dp[i];
        }
        if (i == days.size()) {
            return 0;
        }
        int ans = INT32_MAX;
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.size() && days[i] + durations[k] > days[j]) {
                j++;
            }
            ans = min(ans, costs[k] + f(days, costs, j, dp));
            dp[i] = ans;
        }
        return ans;
    }
};

//严格位置依赖